﻿using System;
using System.Diagnostics;

class Fibonacci
{
    static long FibonacciRecursive(int n)
    {
        if (n <= 1) return n;
        return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
    }

    static long FibonacciIterative(int n)
    {
        if (n <= 1) return n;
        long a = 0, b = 1;
        for (int i = 2; i <= n; i++)
        {
            long c = a + b;
            a = b;
            b = c;
        }
        return b;
    }

    static void Main()
    {
        int n = 40;
        Stopwatch sw = new Stopwatch();

        sw.Start();
        Console.WriteLine($"Recursive: {FibonacciRecursive(n)}");
        sw.Stop();
        Console.WriteLine($"Time: {sw.ElapsedMilliseconds} ms");

        sw.Restart();
        Console.WriteLine($"Iterative: {FibonacciIterative(n)}");
        sw.Stop();
        Console.WriteLine($"Time: {sw.ElapsedMilliseconds} ms");
    }
}